<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>换硬币或者爬梯子</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="换硬币或者爬梯子">换硬币或者爬梯子</h1>
<h1 id="1-将target兑换硬币-要求数目最小">1. 将target兑换硬币， 要求数目最小</h1>
<p>对应的问题是  322. Coin Change <a href="https://leetcode.com/problems/coin-change/">https://leetcode.com/problems/coin-change/</a></p>
<h2 id="11-dp-with-m-x-n-矩阵">1.1 dp with m x n 矩阵</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=Y0ZqKpToTic&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=5">https://www.youtube.com/watch?v=Y0ZqKpToTic&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=5</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">coinChange</span><span class="hljs-params">(self, coins: List[int], amount: int)</span> -&gt; int:</span>
        coins.sort()
        m = len(coins)
        dp = [[<span class="hljs-number">0</span>] + [amount + <span class="hljs-number">1</span>] * amount  <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]

        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, <span class="hljs-number">1</span>+m):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, <span class="hljs-number">1</span>+amount):
                <span class="hljs-keyword">if</span> j &lt; coins[i<span class="hljs-number">-1</span>]:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j]
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = min(dp[i<span class="hljs-number">-1</span>][j], <span class="hljs-number">1</span> + dp[i][j-coins[i<span class="hljs-number">-1</span>]])
        <span class="hljs-comment">#pprint(dp,width=60)</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span> <span class="hljs-keyword">if</span> dp[m][amount] == amount + <span class="hljs-number">1</span> <span class="hljs-keyword">else</span> dp[m][amount]
        
        
</div></code></pre>
<p><img src="pics/dp4.png" alt="dp4.png"></p>
<h2 id="12-dp-with-一维数组">1.2 dp with 一维数组</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=NJuKJ8sasGk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=11">https://www.youtube.com/watch?v=NJuKJ8sasGk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=11</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CoinChangingMinimumCoin.java</a></li>
</ul>
<p><img src="pics/dp7.png" alt="dp7.png"></p>
<p>注意，这里另外用了一个数组last记录solution对应的最后一个硬币种类。 例如13需要用2个硬币，对应的最后一个硬币种类是3(value是6)
13 - 6 = 7， 继续查表，可以看见7需要1个硬币，对应的种类是0(value是7)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">coinChange</span><span class="hljs-params">(self, coins: List[int], amount: int)</span> -&gt; int:</span>
        coins.sort()
        dp = [<span class="hljs-number">0</span>] + [amount+<span class="hljs-number">1</span>] * amount
        last = [<span class="hljs-number">-1</span>] * (amount+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, amount+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> coins:
                <span class="hljs-keyword">if</span> i &lt; coin:
                    <span class="hljs-keyword">break</span>
                <span class="hljs-keyword">else</span>:
                    dp[i] = min(dp[i], dp[i-coin]+<span class="hljs-number">1</span>)
                    last[i] = coin
        <span class="hljs-comment">#print(last)</span>
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span> <span class="hljs-keyword">if</span> dp[amount] == amount+<span class="hljs-number">1</span> <span class="hljs-keyword">else</span> dp[amount]
</div></code></pre>
<h2 id="13-解法">(1.3) 解法</h2>
<pre><code><code><div>class Solution:
    def coinChange(self, coins: List[int], amount: int) -&gt; int:
        if amount == 0:
            return 0
        coins.sort(reverse=True)
        matrix = [0] * (amount+1)
        for i in range(1,amount+1):
            for coin in coins:
                if i == coin or (i&gt;coin and matrix[i-coin]):
                    if matrix[i] == 0:
                        matrix[i] = matrix[i-coin] + 1
                    else:
                        matrix[i] = min(matrix[i], matrix[i-coin] + 1)

        return matrix[amount] if matrix[amount] else -1
</div></code></code></pre>
<h2 id="14">(1.4)</h2>
<p>上面的代码细节处理得还是比较复杂，可以更简单一些，就是初始值不要是0， 而是amount+1, 这样判断更简单。
<a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-xiang-jie</a></p>
<pre><code><code><div>int coinChange(vector&lt;int&gt;&amp; coins, int amount) {
    vector&lt;int&gt; dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 0; i &lt; dp.size(); i++) {
        // 内层 for 在求所有子问题 + 1 的最小值
        for (int coin : coins) {
            if (i - coin &lt; 0) continue;       # 如果之前对coins进行了排序，那么这里的continue可以改为break
            dp[i] = min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}
</div></code></code></pre>
<h2 id="15-下面是我的解法">(1.5) 下面是我的解法。</h2>
<p>和上面(1.2)比起来</p>
<ul>
<li>我的初始值是float('inf'), 不如(1.2)里面的 amount+1 好</li>
<li>我的判断条件 i&lt; coin 直接break, 比(1.2) 里面的continue要好</li>
</ul>
<pre><code><code><div>class Solution:
    def coinChange(self, coins: List[int], amount: int) -&gt; int:
        coins.sort()
        dp = [0] + [float('inf')] * amount
        for i in range(1, amount+1):
            for coin in coins:
                if i &lt; coin:
                    break
                else:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        
        if dp[amount] != float('inf'):
            return dp[amount]
        else:
            return -1
</div></code></code></pre>
<h2 id="16-今天看见一个类似的题目-有更好的解法">1.6 今天看见一个类似的题目, 有更好的解法</h2>
<p>BST + DP</p>
<ul>
<li><a href="https://zhuanlan.zhihu.com/p/136716105">https://zhuanlan.zhihu.com/p/136716105</a></li>
</ul>
<h2 id="17-top-to-bottom-dfs--memo">1.7 top to bottom, dfs + memo</h2>
<p>提交以后会超时...</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">coinChange</span><span class="hljs-params">(self, coins: List[int], amount: int)</span> -&gt; int:</span>
        
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(remain, num)</span>:</span>
            <span class="hljs-keyword">if</span> remain == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> num
            ans = amount+<span class="hljs-number">1</span>
            <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> coins:
                <span class="hljs-keyword">if</span> coin &lt;= remain:
                    ans = min(ans, _dfs(remain - coin, num+<span class="hljs-number">1</span>))
            <span class="hljs-keyword">return</span> ans
        
        r = _dfs(amount, <span class="hljs-number">0</span>)
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span> <span class="hljs-keyword">if</span> r == amount+<span class="hljs-number">1</span> <span class="hljs-keyword">else</span> r
</div></code></pre>
<h2 id="18-今天看到了类似的变形题目-lc-983">1.8 今天看到了类似的变形题目 LC 983</h2>
<ul>
<li><a href="https://leetcode.com/problems/minimum-cost-for-tickets/">https://leetcode.com/problems/minimum-cost-for-tickets/</a></li>
</ul>
<p>官方答案， top -&gt; bottom</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mincostTickets</span><span class="hljs-params">(self, days, costs)</span>:</span>
        dayset = set(days)
        durations = [<span class="hljs-number">1</span>, <span class="hljs-number">7</span>, <span class="hljs-number">30</span>]

<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i)</span>:</span>
            <span class="hljs-keyword">if</span> i &gt; <span class="hljs-number">365</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
            <span class="hljs-keyword">elif</span> i <span class="hljs-keyword">in</span> dayset:
                <span class="hljs-keyword">return</span> min(dp(i + d) + c
                           <span class="hljs-keyword">for</span> c, d <span class="hljs-keyword">in</span> zip(costs, durations))
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">return</span> dp(i + <span class="hljs-number">1</span>)

        <span class="hljs-keyword">return</span> dp(<span class="hljs-number">1</span>)
</div></code></pre>
<p>第二个官方答案，和我的思路一样。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mincostTickets</span><span class="hljs-params">(self, days, costs)</span>:</span>
        N = len(days)
        durations = [<span class="hljs-number">1</span>, <span class="hljs-number">7</span>, <span class="hljs-number">30</span>]

<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i)</span>:</span> <span class="hljs-comment"># How much money to do days[i]+</span>
            <span class="hljs-keyword">if</span> i &gt;= N: <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>

            ans = float(<span class="hljs-string">'inf'</span>)
            j = i
            <span class="hljs-keyword">for</span> c, d <span class="hljs-keyword">in</span> zip(costs, durations):
                <span class="hljs-keyword">while</span> j &lt; N <span class="hljs-keyword">and</span> days[j] &lt; days[i] + d:
                    j += <span class="hljs-number">1</span>
                ans = min(ans, dp(j) + c)

            <span class="hljs-keyword">return</span> ans

        <span class="hljs-keyword">return</span> dp(<span class="hljs-number">0</span>)
</div></code></pre>
<p>我的答案  bottom -&gt; top</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">mincostTickets</span><span class="hljs-params">(self, days: List[int], costs: List[int])</span> -&gt; int:</span>
        n = len(days)
        m = len(costs)
        ranges = [<span class="hljs-number">1</span>, <span class="hljs-number">7</span>, <span class="hljs-number">30</span>]
        dp = [float(<span class="hljs-string">'inf'</span>)] * (n+<span class="hljs-number">1</span>) 
        dp[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>
        <span class="hljs-comment">#print(f"n={n} m={m} dp={dp}")</span>
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(j, n+<span class="hljs-number">1</span>):
                    <span class="hljs-keyword">if</span> days[k<span class="hljs-number">-1</span>] - days[j<span class="hljs-number">-1</span>] &gt;= ranges[i<span class="hljs-number">-1</span>]:
                        <span class="hljs-keyword">break</span>
                    <span class="hljs-comment">#print(f"k={k} i={i} j={j}")</span>
                    dp[k] = min(dp[k], costs[i<span class="hljs-number">-1</span>] + dp[j<span class="hljs-number">-1</span>])            
        <span class="hljs-keyword">return</span> dp[n]
    
</div></code></pre>
<h1 id="2-有多少种不同的硬币组合方法相同数目的同种硬币算一种">2. 有多少种不同的硬币组合方法(相同数目的同种硬币算一种)</h1>
<h2 id="21-对应的问题是518-coin-change-2-httpsleetcodecomproblemscoin-change-2">2.1 对应的问题是518. Coin Change 2   <a href="https://leetcode.com/problems/coin-change-2/">https://leetcode.com/problems/coin-change-2/</a></h2>
<pre><code><code><div>Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
</div></code></code></pre>
<h3 id="22-from-top-to-bottom-dfs--memo">2.2 from top to bottom, dfs + memo</h3>
<p>注意我们求解的时候，因为要排序，所以需要一个辅助函数_helper, 里面有个参数max_coin, 出现的组合方法里面最大硬币面值不能超过max_coin, 以此来确保相同数目同种硬币的组合算一种。</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">change</span><span class="hljs-params">(self, amount: int, coins: List[int])</span> -&gt; int:</span>
        
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(max_coin, amount)</span>:</span>  <span class="hljs-comment"># return number of plans which all coins &lt;= max_coin</span>
            <span class="hljs-keyword">if</span> amount == <span class="hljs-number">0</span>:
                <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
            r = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> self.coins:
                <span class="hljs-keyword">if</span> coin &gt; max_coin:
                    <span class="hljs-keyword">break</span>
                <span class="hljs-keyword">if</span> coin &lt;= amount:
                    r += _helper(coin, amount-coin)
            <span class="hljs-keyword">return</span> r

        <span class="hljs-keyword">if</span> amount == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> coins:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        
        coins.sort()
        self.coins = coins
        <span class="hljs-keyword">return</span> _helper(coins[<span class="hljs-number">-1</span>], amount)
</div></code></pre>
<h3 id="23-from-bottom-to-top-dp-m-x-n-矩阵">2.3 from bottom to top, dp, m x n 矩阵</h3>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">change</span><span class="hljs-params">(self, amount: int, coins: List[int])</span> -&gt; int:</span>
        <span class="hljs-string">'''
        dp[i][j] : the number of combinations to make up amount j by using the first i types of coins
State transition:

not using the ith coin, only using the first i-1 coins to make up amount j, then we have dp[i-1][j] ways.
using the ith coin, since we can use unlimited same coin, we need to know how many ways to make up amount j - coins[i-1] by using first i coins(including ith), which is dp[i][j-coins[i-1]]
        '''</span>
        
        m = len(coins)
        n = amount
        dp = [[<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m+<span class="hljs-number">1</span>):
            dp[i][<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> j &gt;= coins[i<span class="hljs-number">-1</span>]:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j] + dp[i][j - coins[i<span class="hljs-number">-1</span>]]
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j]
        <span class="hljs-keyword">return</span> dp[m][n]
    
</div></code></pre>
<p>注意，上面的二重循环的顺序是可以交换的。 也就是改成下面这样， 但是一旦压缩成一维向量，就不能交换顺序了。</p>
<pre><code class="language-python"><div>        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
                <span class="hljs-keyword">if</span> j &gt;= coins[i<span class="hljs-number">-1</span>]:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j] + dp[i][j - coins[i<span class="hljs-number">-1</span>]]
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = dp[i<span class="hljs-number">-1</span>][j]
        <span class="hljs-keyword">return</span> dp[m][n]
    
</div></code></pre>
<h3 id="24-from-bottom-to-top-dp--一维数组">2.4 from bottom to top, dp   , 一维数组</h3>
<p>看了答案，有人的解法非常简单, 也很巧妙! 外循环是coin, 挨个求同种硬币组成的方案。</p>
<p>这种解法也是把一个m x n 矩阵压缩到一维数组的解法</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">coin_plan2</span><span class="hljs-params">(coins, amount)</span>:</span>

    dp = [<span class="hljs-number">1</span>] + [<span class="hljs-number">0</span>] * amount
    <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> coins:
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(amount-coin+<span class="hljs-number">1</span>):
            dp[i+coin] += dp[i]

    pprint(dp)
    <span class="hljs-keyword">return</span> dp[amount]
</div></code></pre>
<h2 id="22-如果要求的不是总的数目而是具体的组合可能-把上面的代码稍微改变一下就可以了">2.2 如果要求的不是总的数目，而是具体的组合可能。  把上面的代码稍微改变一下就可以了。</h2>
<ol>
<li>Combination Sum</li>
</ol>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">combinationSum</span><span class="hljs-params">(self, candidates: List[int], target: int)</span> -&gt; List[List[int]]:</span>
        dp = defaultdict(list)
        dp[<span class="hljs-number">0</span>] = [[]]
        <span class="hljs-keyword">for</span> candidate <span class="hljs-keyword">in</span> candidates:
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(target + <span class="hljs-number">1</span>):
                <span class="hljs-keyword">for</span> solution_j <span class="hljs-keyword">in</span> dp[i]:
                    dp[i+candidate].append(solution_j+[candidate])
        <span class="hljs-keyword">return</span> dp[target]
</div></code></pre>
<h1 id="3-有多少种不同的硬币组合方法-相同数目的同种硬币出现顺序不同算不同组合-coin3">3. 有多少种不同的硬币组合方法, 相同数目的同种硬币，出现顺序不同算不同组合。 coin3</h1>
<p>这就类似于上台阶的dp算法了。</p>
<pre><code><code><div>Input: amount = 5, coins = [1, 2, 5]
Output: 9
Explanation: there are four ways to make up the amount:
5=5
5=1+2+2
5=2+1+2
5=2+2+1
5=1+1+1+2
5=1+1+2+1
5=1+2+1+1
5=2+1+1+1
5=1+1+1+1+1

f(n) = f(n-1) + f(n-2) + f(n-5)
f(0) = 1
f(1) = 1
f(2) = f(1) + f(0) = 2
f(3) = f(2) + f(1) = 3 
f(4) = f(3) + f(2) = 5
f(5) = f(4) + f(3) + f(0) = 9
</div></code></code></pre>
<p>我们回过头来看，coin_plan3 和 coin_plan2 的主要区别就是2重循环交换了位置!</p>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">coin_plan3</span><span class="hljs-params">(coins, amount)</span>:</span>
    dp = [<span class="hljs-number">1</span>] + [<span class="hljs-number">0</span>] * (amount+max(coins))
    <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(amount):
        <span class="hljs-keyword">for</span> coin <span class="hljs-keyword">in</span> coins:
            dp[i+coin] += dp[i]

    pprint(dp)
    <span class="hljs-keyword">return</span> dp[amount]
</div></code></pre>
<p>这道题好像是能用一维数组处理，没有矩阵dp的方法</p>
<h1 id="4今天又出现了类似于硬币的题目和coin_plan2类似但是是倒序相加的">4.今天又出现了类似于硬币的题目，和coin_plan2类似，但是是倒序相加的</h1>
<h2 id="41-494-target-sum">4.1 494. Target Sum</h2>
<ul>
<li><a href="https://leetcode.com/problems/target-sum/">https://leetcode.com/problems/target-sum/</a></li>
<li><a href="https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation">https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation</a></li>
</ul>
<h2 id="42-1049-last-stone-weight-ii">4.2 1049. Last Stone Weight II</h2>
<ul>
<li><a href="https://leetcode.com/problems/last-stone-weight-ii/">https://leetcode.com/problems/last-stone-weight-ii/</a></li>
</ul>
<h2 id="43-力扣杯-lcp-07传递信息">4.3 力扣杯 LCP 07.传递信息</h2>
<ul>
<li><a href="https://zhuanlan.zhihu.com/p/142050163">https://zhuanlan.zhihu.com/p/142050163</a></li>
</ul>
<h1 id="5-cutting-rod-dynamic-programming">5. Cutting Rod dynamic programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=IRwVmTmN6go&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=10">https://www.youtube.com/watch?v=IRwVmTmN6go&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=10</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CuttingRod.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CuttingRod.java</a></li>
</ul>
<p><img src="pics/dp6.png" alt="dp6.png"></p>

    </body>
    </html>